

/*
 * myRBMap.h
 * 红黑树 map
 * westice 2012-8-31
 */

 
#include "myRBMap.h" 


myRBMapNode getNullNode(int key,int v){
	myRBMapNode testNode;
	testNode.parentNode = NULL;
	testNode.leftSonNode = NULL;
	testNode.rightSonNode = NULL;
	testNode.nodeColor = colorNoDefine;
	testNode.nodeLRonP = lrNoDefine;
	testNode.nodeInvalid = 1;
	testNode.iKey = key;
	return testNode;
}

myRBMap* createMyRBMap(){
	myRBMap* map = (myRBMap*)malloc(sizeof(myRBMap));
	map->rootNode = NULL;
	map->nodeCount = 0;
	return map;
}

void releaseMyRBMap(myRBMap* rbMap){  //释放全部内存


}

myRBNodeColor checkNodeColor(myRBMapNode* node){
	//检查node颜色，NULL为黑色
	
	if(node == NULL){
		return myRBNodeBlack;
	}else{
		return node->nodeColor;
	}
}

myRBMapNode* myRBNodeParent(myRBMapNode* node){
	return node->parentNode;
}

myRBMapNode* myRBNodeGrand(myRBMapNode* node){
	MYASSERT(node->parentNode != NULL)
	return node->parentNode->parentNode;
}

myRBMapNode* myRBNodeUncle(myRBMapNode* node){
	MYASSERT(node->parentNode != NULL)
	MYASSERT(myRBNodeGrand(node) != NULL)
	if(node->parentNode->nodeLRonP == myRBNodeLeft){
		return myRBNodeGrand(node)->rightSonNode;
	}else{
		return myRBNodeGrand(node)->leftSonNode;
	}
}

//左旋
myRBMapNode* myRBLeftPinwheel(myRBMapNode* pivot){
	MYASSERT(pivot != NULL)
	myRBMapNode* pivotParent = myRBNodeParent(pivot);
	myRBNodeLRonP pivotLR = pivot->nodeLRonP;         //左右属性
	myRBMapNode* pivotRightSon = pivot->rightSonNode;
	MYASSERT(pivotRightSon != NULL)
	myRBMapNode* rightLeftSon = pivotRightSon->leftSonNode;
	
	if(pivotParent != NULL){
		if(pivotLR == myRBNodeLeft){
			pivotParent->leftSonNode = pivotRightSon;
		}else{
			pivotParent->rightSonNode = pivotRightSon;
		}
	}
	
	pivotRightSon->parentNode = pivotParent;
	pivotRightSon->nodeLRonP = pivotLR;
	pivotRightSon->leftSonNode = pivot;
	pivot->parentNode = pivotRightSon;
	pivot->rightSonNode = rightLeftSon;
	pivot->nodeLRonP = myRBNodeLeft;
	
	if(rightLeftSon != NULL){
		rightLeftSon->nodeLRonP = myRBNodeRight;
		rightLeftSon->parentNode = pivot;
	}
	//返回pivotRightSon，可能会作为新的根节点
	if(pivotParent == NULL){
		return pivotRightSon;
	}
	return NULL;
}

//右旋
myRBMapNode* myRBRightPinwheel(myRBMapNode* pivot){
	MYASSERT(pivot != NULL)
	myRBMapNode* pivotParent = myRBNodeParent(pivot);
	myRBNodeLRonP pivotLR = pivot->nodeLRonP;         //左右属性
	myRBMapNode* pivotLeftSon = pivot->leftSonNode;
	MYASSERT(pivotLeftSon != NULL)
	myRBMapNode* leftRightSon = pivotLeftSon->rightSonNode;
	
	if(pivotParent != NULL){
		if(pivotLR == myRBNodeLeft){
			pivotParent->leftSonNode = pivotLeftSon;
		}else{
			pivotParent->rightSonNode = pivotLeftSon;
		}
	}
	pivotLeftSon->parentNode = pivotParent;
	pivotLeftSon->nodeLRonP = pivotLR;
	pivotLeftSon->rightSonNode = pivot;
	pivot->parentNode = pivotLeftSon;
	pivot->leftSonNode = leftRightSon;
	pivot->nodeLRonP = myRBNodeRight;
	
	if(leftRightSon != NULL){
		leftRightSon->nodeLRonP = myRBNodeLeft;
		leftRightSon->parentNode = pivot;
	}
	//
	if(pivotParent == NULL){
		return pivotLeftSon;
	}
	return NULL;
}

void myRBFeatureAdjust(myRBMap* rbMap,myRBMapNode* node){
	
	//调整node的红黑特性
	MYASSERT(checkNodeColor(node) == myRBNodeRed)
	if(checkNodeColor(node) != myRBNodeRed){
		printf("this has problem : ");
		printRBMapNode(node);
	}
	
	if(myRBNodeParent(node) == NULL){
		//node为根节点，直接变黑
		node->nodeColor = myRBNodeBlack;
		return;
	}
	if(myRBNodeGrand(node) == NULL){
		//父为根节点
		return;
	}

	if(checkNodeColor(node->parentNode) == myRBNodeBlack){
		//如果父为黑，则不用变性质
	}else{
		myRBMapNode* gNode = myRBNodeGrand(node);
		myRBMapNode* pNode = myRBNodeParent(node);
		myRBMapNode* uNode = myRBNodeUncle(node);
		if(checkNodeColor(uNode) == myRBNodeBlack){
			//如果父为红，叔叔为黑
			if(pNode->nodeLRonP == myRBNodeLeft){
				//父为左子
				if(node->nodeLRonP == myRBNodeLeft){
					//node为左子
					//父变黑，祖父变红，然后祖父右旋
					pNode->nodeColor = myRBNodeBlack;
					gNode->nodeColor = myRBNodeRed;
					myRBMapNode* newRoot = myRBRightPinwheel(gNode);
					if(newRoot != NULL)rbMap->rootNode = newRoot;  //更新根节点
				}else{
					//node为右子
					//父节点左旋，然后调整父节点
					myRBMapNode* newRoot = myRBLeftPinwheel(pNode);
					if(newRoot != NULL)rbMap->rootNode = newRoot; 
					MYASSERT(checkNodeColor(pNode) == myRBNodeRed)
					myRBFeatureAdjust(rbMap,pNode);
				}
			}else{
				//父为右子
				if(node->nodeLRonP == myRBNodeLeft){
					//node为左子
					//父节点右旋，然后调整父节点
					myRBMapNode* newRoot = myRBRightPinwheel(pNode);
					if(newRoot != NULL)rbMap->rootNode = newRoot; 
					MYASSERT(checkNodeColor(pNode) == myRBNodeRed)
					myRBFeatureAdjust(rbMap,pNode);
				}else{
					//node为右子
					//父变黑，祖父变红，然后祖父左旋
					pNode->nodeColor = myRBNodeBlack;
					gNode->nodeColor = myRBNodeRed;
					myRBMapNode* newRoot = myRBLeftPinwheel(gNode);
					printf("newRoot:%d\n",newRoot);
					if(newRoot != NULL)rbMap->rootNode = newRoot; 
				}
			}
			
		}else{
			//父为红，叔叔为红，则父叔变黑，祖父变红，然后调整祖父
			pNode->nodeColor = myRBNodeBlack;
			uNode->nodeColor = myRBNodeBlack;
			gNode->nodeColor = myRBNodeRed;
			MYASSERT(checkNodeColor(gNode) == myRBNodeRed)
			myRBFeatureAdjust(rbMap,gNode);
		}

	}
}


//在pnode节点下插入snode
void insertItemAt(myRBMap* rbMap,myRBMapNode* pnode,myRBMapNode* snode){
	MYASSERT(pnode != NULL)
	MYASSERT(snode != NULL)
	MYASSERT(snode->iKey != pnode->iKey)
	MYASSERT(checkNodeColor(snode) == myRBNodeRed)
	if(snode->iKey < pnode->iKey){
		//插入左子
		if(pnode->leftSonNode == NULL){
			pnode->leftSonNode = snode;
			snode->parentNode = pnode;
			snode->nodeLRonP = myRBNodeLeft;
			myRBFeatureAdjust(rbMap,snode);        //红黑性质调整
		}else{
			insertItemAt(rbMap,pnode->leftSonNode,snode);
		}
	}else if(snode->iKey > pnode->iKey){
		//插入右子
		if(pnode->rightSonNode == NULL){
			pnode->rightSonNode = snode;
			snode->parentNode = pnode;
			snode->nodeLRonP = myRBNodeRight;
			myRBFeatureAdjust(rbMap,snode);
		}else{
			insertItemAt(rbMap,pnode->rightSonNode,snode);
		}
	}
	
}

void myRBMapAddItem(myRBMap* rbMap,myRBMapNode* node){
	//插入前检测是否有node 的key值，有则报错
	myRBMapNode* hasNode = myRBMapFindItemWithiKey(rbMap,node->iKey);
	if(hasNode){
		printf("rbMap has the ikey:%d  not insert it\n",node->iKey);
		return;
	}
	
	//插入节点副本，原node不受我控制
	myRBMapNode* newNode = (myRBMapNode*)malloc(sizeof(myRBMapNode));
	memcpy(newNode,node,sizeof(myRBMapNode));
	
	//插入时新节点标为红色
	newNode->nodeColor = myRBNodeRed;
	if(rbMap->rootNode == NULL){
		newNode->parentNode = NULL;
		newNode->leftSonNode = NULL;
		newNode->rightSonNode = NULL;
		rbMap->rootNode = newNode;   //插入到根节点
		rbMap->rootNode->nodeColor = myRBNodeBlack;
	}else{
		insertItemAt(rbMap,rbMap->rootNode,newNode);
		
	}
}

//在node 下找到iKey的节点
myRBMapNode* findItemAt(myRBMapNode* node,int iKey){
	if(iKey < node->iKey){
		//左子查找
		if(node->leftSonNode == NULL){
			return NULL;
		}else{
			return findItemAt(node->leftSonNode,iKey);
		}
	}
	if(iKey == node->iKey){
		//找到
		return node;
	}
	if(iKey > node->iKey){
		//右子查找
		if(node->rightSonNode == NULL){
			return NULL;
		}else{
			return findItemAt(node->rightSonNode,iKey);
		}
	}
}

myRBMapNode* myRBMapFindItemWithiKey(myRBMap* rbMap,int iKey){
	if(rbMap->rootNode == NULL){
		return NULL;
	}else{
		return findItemAt(rbMap->rootNode,iKey);
	}
}

void myRBMapRemoveItem(myRBMap* rbMap){    //预删除节点，不释放内存

}

void myRBMapRleaseInvalidItem(myRBMap* rbMap){  //删除无效节点，并释放内存

}

void myRBMapRemoveAll(myRBMap* rbMap){     //预删除所有节点，不释放内存


}


void printRBMapNode(myRBMapNode* node){
	printf("item iKey:%d testV:%d color: ",node->iKey,node->testValue);
	if(node->nodeColor == colorNoDefine){
		printf("colorNoDefine ");
	}
	if(node->nodeColor == myRBNodeRed){
		printf("red   ");
	}
	if(node->nodeColor == myRBNodeBlack){
		printf("black ");
	}
	if(node->parentNode != NULL){
		printf("pk:%d ",node->parentNode->iKey);
	}else{
		printf("pk:NULL ");
	}
	if(node->leftSonNode != NULL){
		printf("Lk:%d ",node->leftSonNode->iKey);
	}else{
		printf("Lk:NULL ");
	}
	if(node->rightSonNode != NULL){
		printf("Rk:%d ",node->rightSonNode->iKey);
	}else{
		printf("Rk:NULL ");
	}
	
	printf("\n");
}


void printMidOrder(myRBMapNode* node){
	if(node != NULL){
		printMidOrder(node->leftSonNode);
		printRBMapNode(node);
		printMidOrder(node->rightSonNode);
	}
}

void printMyRBMapMidOrder(myRBMap* rbMap){  // 中序输出 红黑树
	
	myRBMapNode* startNode = rbMap->rootNode;
	if(startNode == NULL)printf("the myRBMap no Item\n");
	printf("print the rbMap 0x%x+++++++++++++++++++\n",rbMap);
	printMidOrder(startNode);
	printf("print end ---------------------------------------------\n");
}






